package com.hy.node;

public class SwapPairs {

    /**
     * 24. 两两交换链表中的节点
     *  给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
     *
     * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     *
     * 输入： head = [1,2,3,4]
     * 输出： 【2，1，4，3】
     *
     *
     *
     */

    // 递归版本
    static ListNode swapPairs(ListNode head){
        if (head == null || head.next == null){
            return head;
        }

        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode listNode = swapPairs(next.next);
        // 这里进行交换
        next.next = head;
        head.next = listNode;
        return next;
    }

/*    static ListNode swapPairs2(ListNode head){
        ListNode dummyNode = null;
        dummyNode = head;
        dummyNode.next = head;
        ListNode prev = dummyNode;

        while (prev.next != null && prev.next.next != null) {
            ListNode temp = head.next.next; // 缓存 next
            prev.next = head.next;          // 将 prev 的 next 改为 head 的 next
            head.next.next = head;          // 将 head.next(prev.next) 的next，指向 head
            head.next = temp;               // 将head 的 next 接上缓存的temp
            prev = head;                    // 步进1位
            head = head.next;               // 步进1位
        }
        return dummyNode.next;

    }*/

    static class ListNode{
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    public static void main(String[] args) {
        ListNode listNode4 = new ListNode(4,null);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);

        System.out.println("移除元素前："+listNode1.toString());
        System.out.println("两两交换元素后："+swapPairs(listNode1));
//        System.out.println("两两交换元素后："+swapPairs2(listNode1));
    }
}
